package com.yun.algorithmproblem.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Leetcode90 {
    public static void main(String[] args) {
        Leetcode90 obj=new Leetcode90();
        int[] nums=new int[]{1,1,2};
        List<List<Integer>> lists = obj.subsetsWithDup(nums);
        System.out.println(lists);
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        int[] bucket = new int[21];
        for (int num : nums) {
            bucket[num + 10]++;
        }
        List<List<Integer>> result = new ArrayList<>();
        dfs(bucket, 0, new LinkedList<>(), result);
        return result;
    }

    private void dfs(int[] bucket, int curr,
                     LinkedList<Integer> stack,
                     List<List<Integer>> result) {
        while (curr <= 20 && bucket[curr] == 0) {
            curr++;
        }
        if (curr > 20) {
            result.add(new ArrayList<>(stack));
            return;
        }
        //选择
        stack.push(curr - 10);
        bucket[curr]--;
        dfs(bucket, curr, stack, result);
        bucket[curr]++;
        stack.pop();
        //不选择
        dfs(bucket, curr + 1, stack, result);
    }
}
